/*
 * @Author: liusheng
 * @Date: 2022-04-12 22:19:49
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-13 12:15:16
 * @Description: 
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 026. 重排链表
给定一个单链表 L 的头节点 head ，单链表 L 表示为：

 L0 → L1 → … → Ln-1 → Ln 
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

 

示例 1:



输入: head = [1,2,3,4]
输出: [1,4,2,3]
示例 2:



输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]
 

提示：

链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000
 

注意：本题与主站 143 题相同：https://leetcode-cn.com/problems/reorder-list/ 
 */

#include <vector>
using namespace std;

struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
};

/*
Time:O(n)
Space:O(n)
to be aborted 
see solution 2 for optimition
*/
class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next)
        {
            return;
        }
        vector<ListNode *> nodeArray;
        ListNode * p = head;
        while (p)
        {
            nodeArray.push_back(p);
            p = p->next;
        }

        int n = nodeArray.size();
        // ListNode * p1 = nodeArray[0];
        // ListNode * p2 = nodeArray[i-1];
        int left = 0;
        int right = n - 1;

        while (left < right)
        {
            nodeArray[left]->next = nodeArray[right];
            //the end's next point must set to nullptr,avoid cycle
            nodeArray[right]->next = nullptr;
            // printf("left val:%d\n",nodeArray[left]->val);
            if (left < right)
            {
                ++left;
            }
            if(left <= right)
            {
                // printf("right val:%d\n",nodeArray[right]->val);
                nodeArray[right]->next = nodeArray[left];
                //the end's next point must set to nullptr,avoid cycle
                nodeArray[left]->next = nullptr;
                --right;
            }
        }
    }
};

//optimize for solution1
//only after the reorder while,reset the last 
//nodeArray[right]->next to nullptr avoid cycle
class Solution2 {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next)
        {
            return;
        }
        vector<ListNode *> nodeArray;
        ListNode * p = head;
        while (p)
        {
            nodeArray.emplace_back(p);
            p = p->next;
        }

        int n = nodeArray.size();
        int left = 0;
        int right = n - 1;

        while (left < right)
        {
            nodeArray[left]->next = nodeArray[right];
            ++left;

            if (left == right)
            {
                break;
            }
            nodeArray[right]->next = nodeArray[left];
            --right;
        }
        //set the last node the next to nullptr,avoid cycle
        nodeArray[right]->next = nullptr;
    }
};

/*
Time:O(n)
Space:O(1)
solution:reverse the second halt,then merge the first half with second half
note: to set the middle->next = nullptr to split the linklist into two list
the middle return the left when the num is even
*/
class Solution3 {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next)
        {
            return;
        }
        
        ListNode * p1 = head;
        ListNode * pMiddle = findMiddleList(head);
        
        //pMiddle is the left one when linklist num is even
        //so p2 = pMiddle->next always keeps the second half
        ListNode * p2 = pMiddle->next;
        //split the origin list into two
        pMiddle->next = nullptr;
        
        //reverse the back halt of the list
        p2 = reverseList(p2);
        
        //merget the two list 
        while (p1 && p2)
        {
            ListNode * p1Next = p1->next;
            p1->next = p2;
            p1 = p1Next;
            
            ListNode * p2Next = p2->next;
            p2->next = p1;
            p2 = p2Next;
        }
    }
private:
    ListNode * reverseList(ListNode * head)
    {
        if (!head || !head->next)
        {
            return head;
        }
        
        ListNode * pre = nullptr;
        ListNode * cur = head;
        while (cur)
        {
            ListNode * next = cur->next;
            cur->next = pre;
            
            pre = cur;
            cur = next;
        }
        
        return pre;
    }
    
    ListNode * findMiddleList(ListNode * head)
    {
        if (!head || !head->next)
        {
            return head;
        }
        
        ListNode * slow = head;
        ListNode * fast = head;
        
        //get the middle node,if node if even,return the left one
        while (fast->next && fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        return slow;
    }
};